package com.zj.base;

/**
 * @program algorithm
 * @description: 选择排序
 * 选择排序是一种简单直观的排序算法，它也是一种交换排序算法，和冒泡排序有一定的相似度，可以认为选择排序是冒泡排序的一种改进。
 *
 * 稳定性
 * 即每次从未排序的数中选择最小的与未排序的第一个交换，破坏了相对顺序，所以不是稳定的排序。
 * 用数组实现的选择排序是不稳定的，用链表实现的选择排序是稳定的。
 * 不过，一般提到排序算法时，大家往往会默认是数组实现，所以选择排序是不稳定的。
 *
 * 适用场景
 * 选择排序实现也比较简单，并且由于在各种情况下复杂度波动小，因此一般是优于冒泡排序的。在所有的完全交换排序中，选择排序也是比较不错的一种算法。但是，由于固有的O(n2)复杂度，选择排序在海量数据面前显得力不从心。因此，它适用于简单数据排序。
 * @author: zhangbo
 * @create: 2022/07/14 01:35
 */
public class SelectSort {

    public static void selectionSort(int[] arr) {
        int temp, min = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            min = i;
            // 循环查找最小值
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            if (min != i) {
                temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }



    private void sort(int[] arr) {
        int num = 0;
        int temp = 0;
        int len = arr.length;

        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                if (arr[num] > arr[j]) {
                    num = j;
                }
            }

            if (i != num) {
                temp = arr[i];
                arr[i] = arr[num];
                arr[num] = temp;
            }

        }

    }
}
